#ifndef GRAPH_HPP
#define GRAPH_HPP

#include <assert.h>
#include <stddef.h>
#include <memory.h>

#if 0
template <class vid_t, class eid_t, int MaxN, int MaxM>
class adjacency_list
{
    struct node
    {
        vid_t degree;       /* numer of adjacent nodes */
        eid_t first_edge;   /* id of the first edge adjacent to the node */
    };

    struct edge
    {
        vid_t v1;           /* id of first vertex; 0=deleted */
        vid_t v2;           /* id of second vertex */
        eid_t next1;        /* id of next edge adjacent to v1, 0=last */
        eid_t next2;        /* id of next edge adjacent to v2, 0=last */
    };

    node   nodes[MaxN+1];   /* nodes[0] is not used */
    size_t num_nodes;
    edge   edges[MaxM+1];   /* edges[0] is not used */
    size_t num_edges;

public:
    adjacency_list() : num_nodes(0), num_edges(0) { }

    void resize(size_t size)
    {
        num_nodes = size;
        memset(nodes, 0, sizeof(nodes[0])*(num_nodes+1));
        num_edges = 0;
    }

    size_t size() const { return num_nodes; }

    eid_t add_edge(vid_t v1, vid_t v2)
    {
        eid_t e = (eid_t)++num_edges;
        nodes[v1].degree++;
        nodes[v2].degree++;

        edges[e].v1 = v1;
        edges[e].v2 = v2;
        edges[e].next1 = nodes[v1].first_edge;
        edges[e].next2 = nodes[v2].first_edge;
        nodes[v1].first_edge = e;
        nodes[v2].first_edge = e;
        return e;
    }

    void remove_edge(eid_t e)
    {
        if (edges[e].v1 != 0) /* edge exists */
        {
            nodes[edges[e].v1].degree--;
            nodes[edges[e].v2].degree--;
            edges[e].v1 = 0;
        }
    }

    size_t degree(vid_t u) const { return nodes[u].degree; }

#if 0
    vid_t next_neighbor(vid_t u, eid_t &e)
    {
        eid_t *pnext = (e == 0)? &nodes[u].first_edge :
                       (edges[e].v2 == u)? &edges[e].next2 : &edges[e].next1;
        e = *pnext;
        while (e)
        {
            if (edges[e].v1 != 0) /* edge exists */
                return (edges[e].v1 ^ edges[e].v2 ^ u);

            /* Update the link to skip deleted edge. */
            *pnext = e = (edges[e].v2 == u)? edges[e].next2 : edges[e].next1;
        }
        return 0;
    }
#elif 0
    vid_t next_neighbor(vid_t u, eid_t &e) const
    {
        do
        {
            e = (e == 0)? nodes[u].first_edge :
                (edges[e].v2 == u)? edges[e].next2 : edges[e].next1;
        } while (e != 0 && edges[e].v1 == 0); /* edge deleted */
        return (e == 0)? 0 : (edges[e].v1 ^ edges[e].v2 ^ u);
    }
#else
    vid_t next_neighbor(vid_t u, eid_t &e) const
    {
        e = (e == 0)? nodes[u].first_edge :
            (edges[e].v2 == u)? edges[e].next2 : edges[e].next1;
        return (e == 0)? 0 : (edges[e].v1 ^ edges[e].v2 ^ u);
    }
#endif
};
#else
template <class vid_t, class eid_t, int MaxN, int MaxM>
class adjacency_list
{
    struct node
    {
        vid_t in_degree;    /* numer of incoming edges */
        vid_t out_degree;   /* number of outgoing edges */
        eid_t first_edge;   /* id of the first adjacent edge; 0=none */
    };

    struct edge
    {
        vid_t peer;         /* id of the peer vertex; 0=deleted */
        eid_t next;         /* id of next adjacent edge; 0=last */
        //eid_t reverse;      /* id of the reverse edge; 0=none */
    };

    node   nodes[MaxN+1];   /* nodes[0] is not used */
    size_t num_nodes;
    edge   edges[MaxM+1];   /* edges[0] is not used */
    size_t num_edges;

public:
    adjacency_list() : num_nodes(0), num_edges(0) { }

    void resize(size_t size)
    {
        num_nodes = size;
        memset(nodes, 0, sizeof(nodes[0])*(num_nodes+1));
        num_edges = 0;
    }

    size_t size() const { return num_nodes; }

    eid_t add_directed_edge(vid_t u, vid_t v)
    {
        assert(num_edges <= MaxM);
        eid_t e = (eid_t)++num_edges;
        nodes[u].out_degree++;
        nodes[v].in_degree++;
        
        edges[e].peer = v;
        edges[e].next = nodes[u].first_edge;
        nodes[u].first_edge = e;
        return e;
    }

#if 0
    eid_t add_edge(vid_t v1, vid_t v2)
    {
        eid_t e = (eid_t)++num_edges;
        nodes[v1].degree++;
        nodes[v2].degree++;

        edges[e].v1 = v1;
        edges[e].v2 = v2;
        edges[e].next1 = nodes[v1].first_edge;
        edges[e].next2 = nodes[v2].first_edge;
        nodes[v1].first_edge = e;
        nodes[v2].first_edge = e;
        return e;
    }
#endif

#if 0
    void remove_edge(eid_t e)
    {
        if (edges[e].v1 != 0) /* edge exists */
        {
            nodes[edges[e].v1].degree--;
            nodes[edges[e].v2].degree--;
            edges[e].v1 = 0;
        }
    }
#endif

#if 0
    size_t degree(vid_t u) const { return nodes[u].degree; }
#endif

#if 0
    vid_t next_neighbor(vid_t u, eid_t &e)
    {
        eid_t *pnext = (e == 0)? &nodes[u].first_edge :
                       (edges[e].v2 == u)? &edges[e].next2 : &edges[e].next1;
        e = *pnext;
        while (e)
        {
            if (edges[e].v1 != 0) /* edge exists */
                return (edges[e].v1 ^ edges[e].v2 ^ u);

            /* Update the link to skip deleted edge. */
            *pnext = e = (edges[e].v2 == u)? edges[e].next2 : edges[e].next1;
        }
        return 0;
    }
#elif 0
    vid_t next_neighbor(vid_t u, eid_t &e) const
    {
        do
        {
            e = (e == 0)? nodes[u].first_edge :
                (edges[e].v2 == u)? edges[e].next2 : edges[e].next1;
        } while (e != 0 && edges[e].v1 == 0); /* edge deleted */
        return (e == 0)? 0 : (edges[e].v1 ^ edges[e].v2 ^ u);
    }
#else
    vid_t next_neighbor(vid_t u, eid_t &e) const
    {
        e = (e == 0)? nodes[u].first_edge : edges[e].next;
        return (e == 0)? 0 : edges[e].peer;
    }
#endif
};
#endif

#endif /* GRAPH_HPP */
